home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / viewers / gif_pas / lzwexp.txt < prev    next >
Text File  |  1988-07-10  |  17KB  |  255 lines
  1.                    LZW and GIF explained----Steve Blackstock
  2.  
  3.  
  4.       I hope this little document will help enlighten those of you out there
  5. who want to know more about the Lempel-Ziv Welch compression algorithm, and,
  6. specifically, the implementation that GIF uses.
  7.      Before we start, here's a little terminology, for the purposes of this
  8. document:
  9.  
  10.       "character": a fundamental data element. In normal text files, this is
  11. just a single byte. In raster images, which is what we're interested in, it's
  12. an index that specifies the color of a given pixel. I'll refer to an arbitray
  13. character as "K".
  14.       "charstream": a stream of characters, as in a data file.
  15.       "string": a number of continuous characters, anywhere from one to very
  16. many characters in length. I can specify an arbitrary string as "[...]K".
  17.       "prefix": almost the same as a string, but with the implication that a
  18. prefix immediately precedes a character, and a prefix can have a length of
  19. zero. So, a prefix and a character make up a string. I will refer to an
  20. arbitrary prefix as "[...]".
  21.       "root": a single-character string. For most purposes, this is a
  22. character, but we may occasionally make a distinction. It is [...]K, where
  23. [...] is empty.
  24.       "code": a number, specified by a known number of bits, which maps to a
  25. string.
  26.       "codestream": the output stream of codes, as in the "raster data"
  27.       "entry": a code and its string.
  28.       "string table": a list of entries; usually, but not necessarily, unique.
  29.       That should be enough of that.
  30.  
  31.      LZW is a way of compressing data that takes advantage of repetition of
  32. strings in the data. Since raster data usually contains a lot of this
  33. repetition, LZW is a good way of compressing and decompressing it.
  34.      For the moment, lets consider normal LZW encoding and decoding. GIF's
  35. variation on the concept is just an extension from there.
  36.      LZW manipulates three objects in both compression and decompression: the
  37. charstream, the codestream, and the string table. In compression, the
  38. charstream is the input and the codestream is the output. In decompression,
  39. the codestream is the input and the charstream is the output. The string table
  40. is a product of both compression and decompression, but is never passed from
  41. one to the other.
  42.      The first thing we do in LZW compression is initialize our string table.
  43. To do this, we need to choose a code size (how many bits) and know how many
  44. values our characters can possibly take. Let's say our code size is 12 bits,
  45. meaning we can store 0->FFF, or 4096 entries in our string table. Lets also
  46. say that we have 32 possible different characters. (This corresponds to, say,
  47. a picture in which there are 32 different colors possible for each pixel.) To
  48. initialize the table, we set code#0 to character#0, code #1 to character#1,
  49. and so on, until code#31 to character#31. Actually, we are specifying that
  50. each code from 0 to 31 maps to a root. There will be no more entries in the
  51. table that have this property.
  52.      Now we start compressing data. Let's first define something called the
  53. "current prefix". It's just a prefix that we'll store things in and compare
  54. things to now and then. I will refer to it as "[.c.]". Initially, the current
  55. prefix has nothing in it. Let's also define a "current string", which will be
  56. the current prefix plus the next character in the charstream. I will refer to
  57. the current string as "[.c.]K", where K is some character. OK, look at the
  58. first character in the charstream. Call it P. Make [.c.]P the current string.
  59. (At this point, of course, it's just the root P.) Now search through the
  60. string table to see if [.c.]P appears in it. Of course, it does now, because
  61. our string table is initialized to have all roots. So we don't do anything.
  62. Now make [.c.]P the current prefix. Look at the next character in the
  63. charstream. Call it Q. Add it to the current prefix to form [.c.]Q, the
  64. current string. Now search through the string table to see if [.c.]Q appears
  65. in it. In this case, of course, it doesn't. Aha! Now we get to do something.
  66. Add [.c.]Q (which is PQ in this case) to the string table for code#32, and
  67. output the code for [.c.] to the codestream. Now start over again with the
  68. current prefix being just the root P. Keep adding characters to [.c.] to form
  69. [.c.]K, until you can't find [.c.]K in the string table. Then output the code
  70. for [.c.] and add [.c.]K to the string table. In pseudo-code, the algorithm
  71. goes something like this:
  72.  
  73.      [1] Initialize string table;
  74.      [2] [.c.] <- empty;
  75.      [3] K <- next character in charstream;
  76.      [4] Is [.c.]K in string table?
  77.       (yes: [.c.] <- [.c.]K;
  78.             go to [3];
  79.       )
  80.       (no: add [.c.]K to the string table;
  81.            output the code for [.c.] to the codestream;
  82.            [.c.] <- K;
  83.            go to [3];
  84.       )
  85.  
  86.        It's as simple as that! Of course, when you get to step [3] and there
  87. aren't any more characters left, you just output the code for [.c.] and throw
  88. the table away. You're done.
  89.       Wanna do an example? Let's pretend we have a four-character alphabet:
  90. A,B,C,D. The charstream looks like ABACABA. Let's compress it. First, we
  91. initialize our string table to: #0=A, #1=B, #2=C, #3=D. The first character is
  92. A, which is in the string table, so [.c.] becomes A. Next we get AB, which is
  93. not in the table, so we output code #0 (for [.c.]),
  94.      and add AB to the string table as code #4. [.c.] becomes B. Next we get
  95. [.c.]A = BA, which is not in the string table, so output code #1, and add BA
  96. to the string table as code #5. [.c.] becomes A. Next we get AC, which is not
  97. in the string table. Output code #0, and add AC to the string table as code
  98. #6. Now [.c.] becomes C. Next we get [.c.]A = CA, which is not in the table.
  99. Output #2 for C, and add CA to table as code#7. Now [.c.] becomes A. Next we
  100. get AB, which IS in the string table, so [.c.] gets AB, and we look at ABA,
  101. which is not in the string table, so output the code for AB, which is #4, and
  102. add ABA to the string table as code #8. [.c.] becomes A. We can't get any more
  103. characters, so we just output #0 for the code for A, and we're done. So, the
  104. codestream is #0#1#0#2#4#0.
  105.       A few words (four) should be said here about efficiency: use a hashing
  106. strategy. The search through the string table can be computationally
  107. intensive, and some hashing is well worth the effort. Also, note that
  108. "straight LZW" compression runs the risk of overflowing the string table -
  109. getting to a code which can't be represented in the number of bits you've set
  110. aside for codes. There are several ways of dealing with this problem, and GIF
  111. implements a very clever one, but we'll get to that.
  112.       An important thing to notice is that, at any point during the
  113. compression, if [...]K is in the string table, [...] is there also. This fact
  114. suggests an efficient method for storing strings in the table. Rather than
  115. store the entire string of K's in the table, realize that any string can be
  116. expressed as a prefix plus a character: [...]K. If we're about to store [...]K
  117. in the table, we know that [...] is already there, so we can just store the
  118. code for [...] plus the final character K.
  119.       Ok, that takes care of compression. Decompression is perhaps more
  120. difficult conceptually, but it is really easier to program.
  121.       Here's how it goes: We again have to start with an initialized string
  122. table. This table comes from what knowledge we have about the charstream that
  123. we will eventually get, like what possible values the characters can take. In
  124. GIF files, this information is in the header as the number of possible pixel
  125. values. The beauty of LZW, though, is that this is all we need to know. We
  126. will build the rest of the string table as we decompress the codestream. The
  127. compression is done in such a way that we will never encounter a code in the
  128. codestream that we can't translate into a string.
  129.       We need to define something called a "current code", which I will refer
  130. to as "<code>", and an "old-code", which I will refer to as "<old>". To start
  131. things off, look at the first code. This is now <code>. This code will be in
  132. the intialized string table as the code for a root. Output the root to the
  133. charstream. Make this code the old-code <old>. *Now look at the next code, and
  134. make it <code>. It is possible that this code will not be in the string table,
  135. but let's assume for now that it is. Output the string corresponding to <code>
  136. to the codestream. Now find the first character in the string you just
  137. translated. Call this K. Add this to the prefix [...] generated by <old> to
  138. form a new string [...]K. Add this string [...]K to the string table, and set
  139. the old-code <old> to the current code <code>. Repeat from where I typed the
  140. asterisk, and you're all set. Read this paragraph again if you just skimmed
  141. it!!!  Now let's consider the possibility that <code> is not in the string
  142. table. Think back to compression, and try to understand what happens when you
  143. have a string like P[...]P[...]PQ appear in the charstream. Suppose P[...] is
  144. already in the string table, but P[...]P is not. The compressor will parse out
  145. P[...], and find that P[...]P is not in the string table. It will output the
  146. code for P[...], and add P[...]P to the string table. Then it will get up to
  147. P[...]P for the next string, and find that P[...]P is in the table, as
  148.      the code just added. So it will output the code for P[...]P if it finds
  149. that P[...]PQ is not in the table. The decompressor is always "one step
  150. behind" the compressor. When the decompressor sees the code for P[...]P, it
  151. will not have added that code to it's string table yet because it needed the
  152. beginning character of P[...]P to add to the string for the last code, P[...],
  153. to form the code for P[...]P. However, when a decompressor finds a code that
  154. it doesn't know yet, it will always be the very next one to be added to the
  155. string table. So it can guess at what the string for the code should be, and,
  156. in fact, it will always be correct. If I am a decompressor, and I see
  157. code#124, and yet my string table has entries only up to code#123, I can
  158. figure out what code#124 must be, add it to my string table, and output the
  159. string. If code#123 generated the string, which I will refer to here as a
  160. prefix, [...], then code#124, in this special case, will be [...] plus the
  161. first character of [...]. So just add the first character of [...] to the end
  162. of itself. Not too bad.  As an example (and a very common one) of this special
  163. case, let's assume we have a raster image in which the first three pixels have
  164. the same color value. That is, my charstream looks like: QQQ.... For the sake
  165. of argument, let's say we have 32 colors, and Q is the color#12. The
  166. compressor will generate the code sequence 12,32,.... (if you don't know why,
  167. take a minute to understand it.) Remember that #32 is not in the initial
  168. table, which goes from #0 to #31. The decompressor will see #12 and translate
  169. it just fine as color Q. Then it will see #32 and not yet know what that
  170. means. But if it thinks about it long enough, it can figure out that QQ should
  171. be entry#32 in the table and QQ should be the next string output.  So the
  172. decompression pseudo-code goes something like:
  173.  
  174.       [1] Initialize string table;
  175.      [2] get first code: <code>;
  176.      [3] output the string for <code> to the charstream;
  177.      [4] <old> = <code>;
  178.      [5] <code> <- next code in codestream;
  179.      [6] does <code> exist in the string table?
  180.       (yes: output the string for <code> to the charstream;
  181.             [...] <- translation for <old>;
  182.             K <- first character of translation for <code>;
  183.             add [...]K to the string table;        <old> <- <code>;  )
  184.       (no: [...] <- translation for <old>;
  185.            K <- first character of [...];
  186.            output [...]K to charstream and add it to string table;
  187.            <old> <- <code>
  188.       )
  189.      [7] go to [5];
  190.  
  191.       Again, when you get to step [5] and there are no more codes, you're
  192. finished.  Outputting of strings, and finding of initial characters in strings
  193. are efficiency problems all to themselves, but I'm not going to suggest ways
  194. to do them here. Half the fun of programming is figuring these things out!
  195.       ---
  196.       Now for the GIF variations on the theme. In part of the header of a GIF
  197. file, there is a field, in the Raster Data stream, called "code size". This is
  198. a very misleading name for the field, but we have to live with it. What it is
  199. really is the "root size". The actual size, in bits, of the compression codes
  200. actually changes during compression/decompression, and I will refer to that
  201. size here as the "compression size". The initial table is just the codes for
  202. all the roots, as usual, but two special codes are added on top of those.
  203. Suppose you have a "code size", which is usually the number of bits per pixel
  204. in the image, of N. If the number of bits/pixel is one, then N must be 2: the
  205. roots take up slots #0 and #1 in the initial table, and the two special codes
  206. will take up slots #4 and #5. In any other case, N is the number of bits per
  207. pixel, and the roots take up slots #0 through #(2**N-1), and the special codes
  208. are (2**N) and (2**N + 1). The initial compression size will be N+1 bits per
  209. code. If you're encoding, you output the codes (N+1) bits at a time to start
  210. with, and if you're decoding, you grab (N+1) bits from the codestream at a
  211. time.  As for the special codes: <CC> or the clear code, is (2**N), and <EOI>,
  212. or end-of-information, is (2**N + 1). <CC> tells the compressor to re-
  213. initialize the string table, and to reset the compression size to (N+1). <EOI>
  214. means there's no more in the codestream.  If you're encoding or decoding, you
  215. should start adding things to the string table at <CC> + 2. If you're
  216. encoding, you should output <CC> as the very first code, and then whenever
  217. after that you reach code #4095 (hex FFF), because GIF does not allow
  218. compression sizes to be greater than 12 bits. If you're decoding, you should
  219. reinitialize your string table when you observe <CC>.  The variable
  220. compression sizes are really no big deal. If you're encoding, you start with a
  221. compression size of (N+1) bits, and, whenever you output the code
  222. (2**(compression size)-1), you bump the compression size up one bit. So the
  223. next code you output will be one bit longer. Remember that the largest
  224. compression size is 12 bits, corresponding to a code of 4095. If you get that
  225. far, you must output <CC> as the next code, and start over.  If you're
  226. decoding, you must increase your compression size AS SOON AS YOU write entry
  227. #(2**(compression size) - 1) to the string table. The next code you READ will
  228. be one bit longer. Don't make the mistake of waiting until you need to add the
  229. code (2**compression size) to the table. You'll have already missed a bit from
  230. the last code.  The packaging of codes into a bitsream for the raster data is
  231. also a potential stumbling block for the novice encoder or decoder. The lowest
  232. order bit in the code should coincide with the lowest available bit in the
  233. first available byte in the codestream. For example, if you're starting with
  234. 5-bit compression codes, and your first three codes are, say, <abcde>,
  235. <fghij>, <klmno>, where e, j, and o are bit#0, then your codestream will start
  236. off like:
  237.  
  238.        byte#0: hijabcde
  239.        byte#1: .klmnofg
  240.  
  241.       So the differences between straight LZW and GIF LZW are: two additional
  242. special codes and variable compression sizes. If you understand LZW, and you
  243. understand those variations, you understand it all!
  244.       Just as sort of a P.S., you may have noticed that a compressor has a
  245. little bit of flexibility at compression time. I specified a "greedy" approach
  246. to the compression, grabbing as many characters as possible before outputting
  247. codes. This is, in fact, the standard LZW way of doing things, and it will
  248. yield the best compression ratio. But there's no rule saying you can't stop
  249. anywhere along the line and just output the code for the current prefix,
  250. whether it's already in the table or not, and add that string plus the next
  251. character to the string table. There are various reasons for wanting to do
  252. this, especially if the strings get extremely long and make hashing difficult.
  253. If you need to, do it.
  254.       Hope this helps out.----steve blackstock
  255.